package com.clps.algorithm.chapter04.两个链表的第一个重合结点;

import com.clps.algorithm.chapter12.链表排序.ListNode;

/**
 * 输入两个单向链表,请问如何找到第一个重合点,如图4.5中的连个链表的第一个重合的结合点的值是4
 */
public class demo01 {
    public static void main(String[] args) {
        
    }
    
    public ListNode getIntersectionNode(ListNode headA,ListNode headB){
        int count1 = countList(headA);
        int count2 = countList(headB);
        int delta = Math.abs(count1 - count2);
       ListNode longer = count1>count2?headA:headB;
       ListNode shorter = count1>count2?headB:headA;
       ListNode nodel = longer;
        for (int i = 0; i <delta ; i++) {
            nodel = nodel.next;
        }

        ListNode node2 = shorter;
        while (nodel!=node2){
            node2 = node2.next;
            nodel = nodel.next;
        }

        return  nodel;
    }

    private int countList(ListNode headA) {
        int count = 0;
        while (headA!=null){
            count++;
            headA = headA.next;
        }
        return  count;
    }
}
